Not Applicable.
Not Applicable.
Not Applicable.
BACKGROUND OF THE INVENTION
This invention relates in general to timing analysis and verification of integrated circuit designs, and in particular to a computer method which enables said analysis to be performed using correlated relationships between the delays that normally occur in components of such circuits.
One of the most important steps in digital design is performing a timing analysis to determine if the circuit meets logic and performance requirements. The essence of such an analysis is determining whether a signal arrives at its destination within some time limit so that it may successfully interact with other signals and logic components. Many signals and time constraints (up to thousands or millions) exist in a modern digital logic chip. The traditional method of timing analysis, pencil and paper, quickly overwhelms a design engineer for a large circuit. Fortunately, the recent past has seen the emergence of computer programs which automate the construction of complex timing models. The designer enters timing and signal information graphically and the program automatically computes whether the circuit meets timing requirements or not. Design optimization can proceed relatively quickly since information does not have to be completely re-entered each time a change is conceived.
Several timing analysis software packages are available on the open market. U.S. Pat. No. 5,576,979 refers to one such product by Chronology(trademark) Corp. Synapticad, Inc. manufactures another one called WaveFormer Pro(trademark). In addition, related products, such as circuit simulators and static timing analyzers, exist which can do timing analysis. These products will be described in greater detail later, especially as they relate to delay correlation.
The critical data entered into a timing analysis includes the signals produced by logic components (or clocks), and the delays associated with these components and their interconnections. Also entered are any timing requirements such as the fact that a signal should arrive at a particular component a certain time before some other signal. Delay times are generally expressed as a range (e.g. 5-10 ns) because there is some uncertainty associated with high volume component manufacture and circuit operating conditions. Delay times are given to the designer by the chip component manufacturer. Traditionally, designers have assumed that the entire uncertainty range for each component should be accounted for independently of the other delays. Therefore, the time difference between any two delays must be calculated assuming that one is at its maximum time and the other at its minimum time. This forces the design to meet a worst-case analysis where the most conservative clock speed is chosen.
However, it is known that components placed on the same circuit have some correlation between their delay times. If one component has an actual delay time at the high end of its uncertainty range, others on the same circuit will tend to be at the high end also. This results from similarities in the manufacturing process used to make the gates, similar operating temperature, and physical proximity. Chip manufacturers are beginning to publish this type of correlation information in their design handbooks. This data is furnished in terms of a correlation factor between two gates, i.e. a percentage or a fraction between 0-1. It is determined by empirical measurements of the delay speeds for gates in a circuit.
Delay correlation allows a better than worst-case analysis to be used in design. This is because correlated gates have a reduced time difference between their outputs. This reduction can be thought of as a time savings which can, in turn, be translated into a corresponding increase in clock speed.
A simple example will better illustrate the concept of delay correlation. FIG. 1 shows two gates each having some propagation delay range. D1 ranges from 5-10 ns and D2 ranges from 0-5 ns. If the two gates have no delay correlation (the usual assumption) then the actual delay times for each could fall anywhere in the shown ranges. For instance, if D1=10 ns, then D2 could have a delay time as low as 0 ns. We will call this condition 0% correlation.
At the other end of the spectrum is 100% correlation. This means that if D1=5 ns, then D2=0 ns. If D1=7.5 ns then D2 will be at 2.5 ns, and so forth. Clearly 100% correlation greatly reduces the difference between the two delays.
What happens for, say, 80% correlation? If D1=5 ns, then D2 will be in the range 0-1 ns. In other words the possible range for D2 spans 20% (100%-80%) of its total range. Now, if D1=10 ns, then D2 would have a range of delay times from 4-5 ns. This is because the D2 range is xc2x120% around 5 ns, it""s corresponding point. Obviously, since a higher delay time than 5 ns is not possible, the range is 4-5 ns rather than 4-6 ns.
By inspecting the table in FIG. 1 we can calculate the minimum and maximum differences between the delays for each correlation factor. For 0% correlation, the difference works out to 0-10 ns, for 100% it is exactly 5 ns, and for 80% it is 4-6 ns. These numbers, tabulated in FIG. 1, illustrate the effect of delay correlation on time differences between events.
The change in these differences as correlation factor increases allows for a faster circuit design. For 100% correlation, the designer knows that D1 will always arrive 5 ns after D2. For 0%, D1 could arrive as much as 10 ns after D2. The uncorrelated circuit is, in effect, 5 ns slower than the perfectly correlated one.
The differences given in FIG. 1 can be arrived at through two equations. The first expresses the minimum time of arrival of D1 with respect to D2:
xcex94min=a1xe2x88x92b2+min[(b1xe2x88x92a1),(b2xe2x88x92a2)]cfxe2x80x83xe2x80x83(1)
The second expresses the maximum time of arrival of D1 with respect to D2:
xcex94max=b1xe2x88x92a2xe2x88x92min[(b1xe2x88x92a1),(b2xe2x88x92a2)]cfxe2x80x83xe2x80x83(2)
Note that negative answers indicate that D1 arrived before D2. Also note that by reversing the sign on each equation, we obtain the time of arrival of D2 with respect to D1.
Given the benefits of delay correlation, it is the purpose of this invention to incorporate a general method for calculating it into computer programs for timing analysis. Although variations on the concept have been incorporated into other timing analysis products, none has done so in the general manner that is proposed here. To confirm this point, a review of the prior art will now be made.
Several timing analysis software packages are and have been available on the open market. The first such product was called dV/dt(copyright) by Engineerium(trademark), a company no longer doing business. The product featured a windowed environment where the user could graphically create timing diagrams and analyze the corresponding timing relationships. No features existed where delay correlation relationships could be entered or calculated, so the product based its timing analysis on a worst-case scenario.
U.S. Pat. No. 5,576,979 refers to another such product by Chronology(trademark) Corp., known as TimingDesigner(copyright). This product also includes a windowed timing diagram editing environment, but in addition has a feature which enables signal skews to be included in the analysis. This feature was developed in attempt to model delay correlation in a specific situation, the case of clock buffers. Because data sheets commonly attach a parameter called skew which related two signals of the buffer, Chronology added a feature to allow entry of a skew value and associated computation to adjust for the reduction of uncertainty between output edges in this particular case. This modeling technique has a serious flaw, however. In particular, signal skews as used in the U.S. Pat. No. 5,576,979 patent can only be applied to entire signals, because they presuppose that a single delay acts on one signal, while another single delay acts on another signal. This is a common situation in a clock buffer, where each buffer gate corresponds to a signal, but the gates are highly correlated with respect to each other because they are part of the same buffer. Thus, a signal skew calculation effectively means the consideration of delay correlation between only two delays. This is a valid representation for common, albeit very simplified, situations. In contrast, the invention described here is capable of analyzing any number of interacting delays in any two paths and the correlation relationships are between delays, not signals.
Another similar product for timing analysis includes Synapticad""s(trademark) WaveFormer Pro(copyright), which has reduced to practice the complete delay correlation analysis as described in this invention. WaveFormer Pro contains additionally a graphical user interface, comprised of a timing diagram editor and dialog boxes, for conveniently entering delay and delay correlation information for any integrated circuit design.
Other products for timing analysis and verification include circuit simulators and timing analyzers, which traditionally have not included delay correlation, but use instead a worst-case analysis. Generally these products are used for post-verification of circuit performance, rather than design. One such product that does include, again a simplified form of delay correlation, is Mentor-Graphics""(trademark) Tau(copyright) product. Like Chronology""s product, this one is also able to perform signal skews, but not multiple correlation between any number of individual delays.
Delay correlation, however, is a known concept in the art of timing analysis and verification. Girodias and Cerny (Girodias, P. and Cerny, E., xe2x80x9cInterface Timing Verification with Delay Correlation Using Constraint Logic Programmingxe2x80x9d, Proceedings of the 1997 European Design and Test Conference) published work in which they use a programming technique known as constraint logic programming to verify timing in integrated circuits. The technique is able to make use of delay correlation, however, it uses an iterative method fundamentally distinct from the one that is described by this invention. In particular, the technique enumerates possible timing values for the components in the circuit and then verifies if these yield a correct timing analysis. By iterating over many such possible values, the algorithm is able to determine whether a timing violation has occurred. Thus, this technique amounts to a xe2x80x9cbrute forcexe2x80x9d walk-through of likely states. Although conceptually sound, this method was avoided here because it is prohibitively expensive in terms of computer time for large circuits (standard workstations begin to perform poorly using the brute force method when as few as eight delays are included in a single computational chain). In Cerny""s paper he discusses analyzing timing diagrams with as many as 50 delays, but these delays are not in a single computational chain and hence are still solvable by brute force techniques. When delays are included in a chain, however, the memory and CPU requirements increase rapidly using the brute force method as additional delays are added. Furthermore, Cerny and Girodias"" method does not handle correlation between timing constraints, such as setups or holds, constraints which can be correlated and taken into account during a correlation analysis.
The method described by this invention is thus unique not only as an idea, but also because it makes better use of computer resources than existing techniques in the prior art.
To overcome limitations in the prior art, and to overcome other limitations that will become apparent upon reading and understanding this specification, the present invention discloses a method of a computer program which automates the entry, modification, and computation of delay correlation effects in digital electronic circuits. This feature is integrated to and works with computer programs which perform many general timing analysis and verification functions. Such computer programs could include timing verification/viewing/editing tools, circuit simulators, or static timing analyzers.